<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>数据结构之二叉树</title>
  </head>
  <body>
    <script type="text/javascript">
      // 节点
      function Node(data) {
        this.data = data;
        this.left = null;
        this.right = null;
      }

      // 二叉搜索树
      function Bst() {
        this.root = null;
        this.insert = insert;
        this.preOrder = preOrder;
        this.inOrder = inOrder;
        this.lastOrder = lastOrder;
        this.iteratePreOrder = iteratePreOrder;
        this.iterateInOrder = iterateInOrder;
        this.iterateLastOrder = iterateLastOrder;
        this.getMin = getMin;
        this.getMax = getMax;
        this.find = find;
        this.remove = remove;
      }

      // 向树中插入数据
      function insert(data) {
        var node = new Node(data);
        if (this.root === null) {
          this.root = node;
        } else {
          var current = this.root;
          var parent;
          while (true) {
            parent = current;
            if (data < current.data) {
              current = current.left;
              if (current === null) {
                parent.left = node;
                break;
              }
            } else {
              current = current.right;
              if (current === null) {
                parent.right = node;
                break;
              }
            }
          }
        }
      }

      /* 插入操作也可以这么写 */
      // 向树中插入数据
      function insert(data) {
        var newNode = new Node(data); // 新节点
        if (this.root === null) {
          this.root = newNode;
        } else {
          insertNode(this.root, newNode);
        }
      }
      // 插入节点方法
      function insertNode(node, newNode) {
        if (newNode.data > node.data) {
          // 往右走
          if (node.right === null) {
            node.right = newNode;
          } else {
            insertNode(node.right, newNode); // 递归
          }
        } else if (newNode.data < node.data) {
          // 往左走
          if (node.left === null) {
            node.left = newNode;
          } else {
            insertNode(node.left, newNode); // 递归
          }
        }
      }

      // 前序遍历：根->左->右
      function preOrder(node, res) {
        if (node) {
          res.push(node.data);
          preOrder(node.left, res);
          preOrder(node.right, res);
        }
        return res;
      }

      // 中序遍历：左->根->右
      function inOrder(node, res) {
        if (node) {
          inOrder(node.left, res);
          res.push(node.data);
          inOrder(node.right, res);
        }
        return res;
      }

      // 后序遍历：左->右->根
      function lastOrder(node, res) {
        if (node) {
          lastOrder(node.left, res);
          lastOrder(node.right, res);
          res.push(node.data);
        }
        return res;
      }

      // 前序遍历的迭代实现
      function iteratePreOrder(node, res) {
        const stack = [];
        while (node || stack.length) {
          // 迭代访问节点的左孩子，并入栈
          while (node) {
            res.push(node.data);
            stack.push(node);
            node = node.left;
          }
          // 如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
          if (stack.length) {
            node = stack.pop();
            node = node.right;
          }
        }
        return res;
      }

      // 中序遍历的迭代实现
      function iterateInOrder(node, res) {
        const stack = [];
        while (node || stack.length) {
          // 迭代访问节点的左孩子，并入栈
          while (node) {
            stack.push(node);
            node = node.left;
          }
          // 如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
          if (stack.length) {
            node = stack.pop();
            res.push(node.data);
            node = node.right;
          }
        }
        return res;
      }

      // 后序遍历的迭代实现
      function iterateLastOrder(node, res) {
        const stack = [];
        let prev = null;
        while (node || stack.length) {
          while (node) {
            stack.push(node);
            node = node.left;
          }
          node = stack.pop();
          if (node.right === null || node.right === prev) {
            res.push(node.data);
            prev = node;
            node = null;
          } else {
            stack.push(node);
            node = node.right;
          }
        }
        return res;
      }

      // 获取树中的最小节点
      function getMin(node) {
        var current = this.root || node;
        while (current.left) {
          current = current.left;
        }
        return current;
      }

      // 获取树中的最大节点
      function getMax(node) {
        var current = this.root || node;
        while (current.right) {
          current = current.right;
        }
        return current;
      }

      // 查找某个数据
      function find(data) {
        var current = this.root;
        while (current) {
          if (data === current.data) {
            return current;
          } else if (data < current.data) {
            current = current.left;
          } else {
            current = current.right;
          }
        }
        return null;
      }

      // 删除某个数据
      function remove(data) {
        removeNode(this.root, data);
      }

      // 删除节点方法
      function removeNode(node, data) {
        if (node === null) {
          return null;
        }
        if (data === node.data) {
          // 叶子节点
          if (node.left === null && node.right === null) {
            return null;
          }
          // 只有右节点
          if (node.left === null) {
            return node.right;
          }
          // 只有左节点
          if (node.right === null) {
            return node.left;
          }
          // 左右节点都有，记住删除后要替换成右子树的最小节点
          var tempNode = getMin(node.right); // 找到右子树的最小节点
          node.data = tempNode.data;
          node.right = removeNode(node.right, tempNode.data);
          return node;
        } else if (data < node.data) {
          node.left = removeNode(node.left, data);
          return node;
        } else {
          node.right = removeNode(node.right, data);
          return node;
        }
      }

      var bst = new Bst();
      bst.insert(23);
      bst.insert(45);
      bst.insert(16);
      bst.insert(37);
      bst.insert(3);
      bst.insert(99);
      bst.insert(22);
      console.log("前序遍历：", bst.preOrder(bst.root, []));
      console.log("非递归前序遍历：", bst.iteratePreOrder(bst.root, []));
      console.log("中序遍历：", bst.inOrder(bst.root, []));
      console.log("非递归中序遍历：", bst.iterateInOrder(bst.root, []));
      console.log("后序遍历：", bst.lastOrder(bst.root, []));
      console.log("非递归后序遍历：", bst.iterateLastOrder(bst.root, []));
      console.log("最小节点：", bst.getMin());
      console.log("最大节点：", bst.getMax());
      bst.remove(16);
      console.log("中序遍历：", bst.inOrder(bst.root, []));
    </script>
  </body>
</html>
